'''
https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/
'''
from typing import Optional, List
from collections import deque

from c06_tree.utils import TreeNode, built_tree_by_complete_tree


class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        q = deque([root])
        res = []
        flag = True
        while q:
            level = []
            level_size = len(q)
            for i in range(level_size):
                cur = q.popleft()
                level.append(cur.val)
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            if flag:
                res.append(level)
            else:
                res.append(level[::-1])
            flag = not flag
        return res







